package problems;


public class Euler206 extends AbstractEuler {

	@Override
	public Number calculate() {
		//the template:				"1_2_3_4_5_6_7_8_9_0";
		long lower = (long)Math.sqrt(1020304050607080900L); //floor(sqrt) = 1010101010
		long upper = (long)Math.sqrt(1929394959697989990L); //floor(sqrt) = 1389026623
		//answer has to be a multiple of 10 for the last digit of the square to be 0, so we can increment by 10 and check all options;
		//the fact that the lower bound is already a multiple of 10 is a happy accident :)
		for (long i = lower; i < upper; i+=10) {
			long square = i*i;
			if ((square % 1000) / 100 == 9 &&
				(square % 100000) / 10000 == 8 &&
				(square % 10000000) / 1000000 == 7 &&
				(square % 1000000000) / 100000000 == 6 &&
				(square % 100000000000L) / 10000000000L == 5 &&
				(square % 10000000000000L) / 1000000000000L == 4 &&
				(square % 1000000000000000L) / 100000000000000L == 3 &&
				(square % 100000000000000000L) / 10000000000000000L == 2
//				(square % 10000000000000000000L) / 1000000000000000000 == 1 //numbers are too big for Long, but that doesn't matter anyway
			) {
				return i;
			} else {
				continue;
			}
		}
		throw new RuntimeException("answer not found before upper limit " + upper);
	}

	@Override
	protected Number getCorrectAnswer() {
		return 1389019170L;
	}

}
